package com.husk.leetcode.tree;

import java.util.Stack;

/**
 * <p>
 *
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/3/22
 */
public class BinaryTreeGeneralFuntion {

    /**
     * 二叉树前序遍历，递归
     *
     * @param node
     */
    public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        } else {
            System.out.println(node.val);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    /**
     * 二叉树前序遍历，非递归
     *
     * @param node
     */
    public void nonRecOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            TreeNode item = stack.pop();
            System.out.println(item.val);
            // 右叶子先入栈，先进后出
            if (item.right != null) {
                stack.push(item.right);
            }
            if (item.left != null) {
                stack.push(item.left);
            }
        }
    }

    /**
     * 二叉树-中序遍历递归
     *
     * @param node
     */
    public void midOrder(TreeNode node) {
        if (node == null) {
            return;
        } else {
            midOrder(node.left);
            System.out.println(node.val);
            midOrder(node.right);
        }
    }

    /**
     * 二叉树-后续遍历递归
     *
     * @param node
     */
    public void postOrder(TreeNode node) {
        if (node == null) {
            return;
        } else {
            preOrder(node.left);
            preOrder(node.right);
            System.out.println(node.val);
        }
    }

    /**
     * 获取二叉树的高度
     *
     * @param node
     * @return
     */
    public int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            int i = this.getHeight(node.left);
            int j = this.getHeight(node.right);
            return Math.max(i, j) + 1;
        }
    }

    /**
     * 获取二叉树的节点数
     *
     * @param node
     * @return
     */
    public int getSize(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + this.getSize(node.left) + this.getSize(node.right);
        }
    }

}
